package algorithm.dp;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 最长数对链 {
    /*
     * 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
     * 
     * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
     * 
     * 给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
     * 
     * 示例 :
     * 
     * 输入: [[1,2], [2,3], [3,4]] 输出: 2 解释: 最长的数对链是 [1,2] -> [3,4] 注意：
     * 
     * 给出数对的个数在 [1, 1000] 范围内。
     */
    public int findLongestChain(int[][] pairs) {
        /**
         * 另外一种思路：很简单，在(c,d)区间内，如果有另外一个数(m,n)如果m>=c,n<=d,那么抛弃(c,d)这个数对
         */
        /*
         * 寻找一个最长递增序列：对于 (c,d) 找到小于c的最长链，加上当前的，和结束为d的d链比较，取最大值
         * 
         * 执行用时 : 355 ms, 在Maximum Length of Pair Chain的Java提交中击败了5.07% 的用户 内存消耗
         * : 84.8 MB, 在Maximum Length of Pair Chain的Java提交中击败了5.62% 的用户
         */
        List<int[]> list = new ArrayList<>();
        for (int[] pair : pairs) {
            list.add(pair);
        }
        Comparator<int[]> compa = new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        };
        list.sort(compa);
        Map<Integer, Integer> chain = new HashMap<>();
        for (int[] pair : list) {
            int c = pair[0];
            int d = pair[1];
            int max = 0;
            for (int b : chain.keySet()) {
                if (b >= c) {
                    continue;
                }
                max = Math.max(chain.getOrDefault(b, 0), max);
            }
            max++;
            chain.put(d, Math.max(chain.getOrDefault(d, 0), max));
        }

        int max = 0;
        for (int val : chain.values()) {
            max = Math.max(val, max);
        }
        return max;
    }

    public int fun2(int[][] pairs) {
        /**
         * 执行用时 : 32 ms, 在Maximum Length of Pair Chain的Java提交中击败了89.13% 的用户 内存消耗
         * : 51.8 MB, 在Maximum Length of Pair Chain的Java提交中击败了50.56% 的用户
         * 进行下一个挑战： 另外一种思路：很简单，在(c,d)区间内，如果有另外一个数(m,n)如果m>=c,n<=d,那么抛弃(c,d)这个数对
         */
        List<int[]> list = new ArrayList<>();
        for (int[] pair : pairs) {
            list.add(pair);
        }
        Comparator<int[]> compa = new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        };
        list.sort(compa);
        int count = 0;
        int preEnd = 1 << 31;
        for (int i = 0; i < list.size(); i++) {
            int[] pair = list.get(i);
            int c = pair[0];
            int d = pair[1];
            if (c > preEnd) {
                // 这个数是可以被加入的，但是否加入要看后面的那一个数
                if (i == list.size() - 1) {
                    count++;
                } else {
                    int[] tp = list.get(i + 1);
                    int n = tp[1];
                    int m = tp[0];
                    if (m >= c && n <= d) {
                        continue;
                    } else {
                        count++;
                        preEnd = d;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        最长数对链 run = new 最长数对链();
        int[][] pairs = { { -6, 9 }, { 1, 6 }, { 8, 10 }, { -1, 4 }, { -6, -2 }, { -9, 8 }, { -5, 3 }, { 0, 3 } };
        System.err.println(run.fun2(pairs));
    }
}
